package com.zbl.小题大做;

/*
有环，快慢指针（在第一次相遇后，快指针指向头，速度改为1，第二次指针相遇即为入环点）。hashSet可解
相交，判断有无交点（链表末尾值是否相同），判段交点位置（长链表先走大于短链表的部分，然后一起走，相同节点的地方就是交点）。hashSet可解
节点数相加，得出新链表数，短链走一遍，长链接着走，拿个变量存进位信息
回文判断，快慢指针，快指针结束，慢指针到中点，慢指针后的链表翻转，同时从头和尾开始走，直到碰头，节点都一直相同，即为回文。stack可解
 */
public class 链表 {

    public static void main(String[] args) {
        RandomNode r1 = new RandomNode(1);
        RandomNode r2 = new RandomNode(2);
        RandomNode r3 = new RandomNode(3);
        RandomNode r4 = new RandomNode(4);
        RandomNode r5 = new RandomNode(5);
        r1.next = r2;
        r2.next = r3;
        r3.next = r4;
        r4.next = r5;
        r1.random = r3;
        r2.random = r5;
        r3.random = r2;
        r4.random = r1;
        r5.random = r4;

        RandomNode clone = cloneLink(r1);
        while (clone != null){
            System.out.println("label: " + clone.label + " random: " + clone.random.label);
            clone = clone.next;
        }
    }

    /*
    链表合并
    合并有序链表数组为一个有序链表
    一、所有链表头节点放入堆，堆弹出最弱节点放入结果链表，弹出节点的子节点放入堆，循环。//
     */

    /*
    克隆含随机指针的链表，链表节点除了next，还有random指针，random指针指向链表中的节点，克隆后，random指针指向克隆后的节点。
    1、克隆链表插入原链表，原节点next指向克隆节点，克隆节点又指向原节点的原next，这样就插入了；克隆节点的random就是原节点的random节点的新next。
    2、原节点和克隆节点分离
    hashMap<旧节点, 新节点>可解
     */
    static class RandomNode {
        int label;
        RandomNode next, random;
        RandomNode(int x) { this.label = x; }
    }
    public static RandomNode cloneLink(RandomNode link) {
        RandomNode head = link;

        // 克隆节点并插入原链表
        RandomNode next = null;
        while(link != null) {
            next = link.next;
            link.next = new RandomNode(link.label);
            link.next.next = next;
            link = next;
        }

        // 克隆节点的random就是原节点的random节点的新next
        link = head;
        while(link != null) {
            link.next.random = link.random.next;
            link = link.next.next;
        }

        // 获取克隆链表头
        RandomNode ans = head.next;

        // 分离原链表和克隆链表
        RandomNode L = head;
        RandomNode R = head.next;
        while(R.next != null){
            L.next = L.next.next;
            R.next = L.next.next;
            L = L.next;
            R = R.next;
        }

        return ans;
    }
}
